package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 * 1593. 拆分字符串使唯一子字符串的数目最大
 *
 * 题型 ： 回溯 - 切割
 * https://leetcode.cn/problems/split-a-string-into-the-max-number-of-unique-substrings/description
 *
 * ```
 * 给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
 *
 * 字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。
 *
 * 注意：子字符串 是字符串中的一个连续字符序列。
 *
 *
 *
 * 示例 1：
 * 输入：s = "ababccc"
 * 输出：5
 * 解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，因为其中的 'a' 和 'b' 都出现了不止一次。
 *
 * 示例 2：
 * 输入：s = "aba"
 * 输出：2
 * 解释：一种最大拆分方法为 ['a', 'ba'] 。
 *
 * 示例 3：
 * 输入：s = "aa"
 * 输出：1
 * 解释：无法进一步拆分字符串。
 *
 *
 * 提示：
 * 1 <= s.length <= 16
 * s 仅包含小写英文字母
 * ```
 */
class leetcode_1593 {

    @Test
    fun test_1() {
        val result = maxUniqueSplit("ababccc")
        val expected = 5
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_2() {
        val result = maxUniqueSplit("aba")
        val expected = 2
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_3() {
        val result = maxUniqueSplit("aa")
        val expected = 1
        Assert.assertEquals(expected, result)
    }

    fun maxUniqueSplit(s: String): Int {
        /**
        回溯 - 切割问题
         */
        val path: ArrayList<String> = ArrayList()
        f(s, 0, path)
        return count
    }

    var count: Int = 0

    fun f(s: String, start: Int, path: ArrayList<String>) {
        // 1 确定函数参数以及返回值
        // 2 终止条件
        if (s.length == 1) {
            count = 1
            return
        }
        if (start > s.length) {
            return
        }
        // 收集结果
        if (start == s.length) {
            if (path.size > count) {
                count = path.size
            }
            // println("path:$path")
            return
        }

        // 3 确认遍历方向
        for (i in start until s.length) {
            // 处理节点
            // TODO:substring
            val sub: String = s.substring(start..i) // [0, i]
            // if(start == 0){
            //     println("start=$start, i = $i, sub=$sub")
            // }
            // TODO:判断是否重复？
            if (path.contains(sub)) {
                continue
            }
            path.add(sub)

            // 递归
            f(s, i + 1, path)

            // 回溯
            path.removeAt(path.size - 1)


            // 4 剪枝 ？
            // 5 去重？
        }
    }
}